package com.LeetCode.String;

import org.junit.Test;

import java.util.Arrays;

/**
 * 最长上升子序列
 */
public class LengthOfLIS {
    public int LengthOfLIS(int[] nums){
        int len = nums.length;
        if(len < 2){
            return len;
        }

        int[] dp = new int[len];
        Arrays.fill(dp,1);

        for(int i = 1; i<len; i++){
            for(int j = 0; j<i; j++){
                if(nums[j] < nums[i])
                    dp[i] = Math.max(dp[i] , dp[j] + 1);
            }
        }

        int res = 0;
        for(int p : dp){
            res = Math.max(p , res);
        }
        return res;
    }

    //搜索 0 ~ r 第一个大于target的数字
    private int binary_search(int[] arr , int r, int target){
        int l = 0;
        int index = 0;
        while(l<r){
            int mid = (l+r) >>> 1;
            if(arr[mid] >= target){
                r = mid - 1;
                index = mid;
            }else{
                l = mid + 1;
            }
        }
        return index;
    }

    public int lengthOfLIS_binary(int[] arr){
        if(arr == null || arr.length == 0) return 0;
        int len = arr.length;
        int res = 0;
        int[] dp = new int[len + 1];
        dp[0] = arr[0];
        for(int i = 1; i < len; i++){
            if(arr[i] > dp[res]){
                dp[++res] = arr[i];
            }else{
                dp[binary_search(dp,res,arr[i])] = arr[i];
            }
        }
        return res+1;
    }

    @Test
    public void test(){
        int[] arr = {10,9,2,5,3,7,101,18};
        System.out.println(binary_search(arr,8,100));
        System.out.println(lengthOfLIS_binary(arr));
    }
}
